
//验证二叉树搜索树
class Solution {
public:
    bool recursion(TreeNode* root,int& judge,bool& flag)
    {
        if(!root){
            return true;
        }
        bool bl = recursion(root->left,judge,flag);
        if(!flag){
            judge = root->val;
            flag = true;
        }
        else{
            if(judge >= root->val)
            bl = false;
            else{
                judge = root->val;
            }
        }
        if(bl)
        bl = recursion(root->right,judge,flag);
        return bl;
    }
    bool isValidBST(TreeNode* root) {
        int judge = 0;
        bool flag = false; //利用这个标记是否第一次给judge赋值，通过比较judge与root->val中的值来判断是否为搜索二叉树
        return recursion(root,judge,flag);
    }
};

//二叉树搜索树中第k小的元素
class Solution {
public:
    bool recursion(TreeNode* root,int& k,int& res)
    {
        if(!k){
            return false; //说明第k小的元素已经找到了
        }
        if(!root){
            return true;
        }
        bool flag = recursion(root->left,k,res);
        if(k){
            res = root->val;
            --k;
        }
        if(flag) //如果找到二叉搜索树中的第k小的元素就不用再继续递归了
        flag = recursion(root->right,k,res);
        return flag;
    }
    int kthSmallest(TreeNode* root, int k) {
        int res = 0;
        recursion(root,k,res);
        return res;
    }
};